#include<bits/stdc++.h>
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,k,ans,a[MAXN];
vector<int> occ[MAXN];
namespace DS {
	struct INFO {int mn,cnt;}t[MAXN<<2];
	int tag[MAXN<<2];
	INFO operator +(INFO A,INFO B) {return {min(A.mn,B.mn),(A.mn<=B.mn)*A.cnt+(A.mn>=B.mn)*B.cnt};}
	INFO operator +(INFO A,int B) {return {A.mn+B,A.cnt};}
	void build(int k,int l,int r) {
		tag[k]=0,t[k]={0,r-l+1};
		if(l!=r) build(lson,l,mid),build(rson,mid+1,r);
		return ;
	}
	void push_down(int k,int l,int r) {return tag[lson]+=tag[k],tag[rson]+=tag[k],t[lson]=t[lson]+tag[k],t[rson]=t[rson]+tag[k],tag[k]=0,void();}
	void update(int k,int l,int r,int x,int y,int v) {
		if(x<=l&&r<=y) return tag[k]+=v,t[k]=t[k]+v,void();
		push_down(k,l,r);
		if(x<=mid) update(lson,l,mid,x,y,v);
		if(y>mid) update(rson,mid+1,r,x,y,v);
		return t[k]=t[lson]+t[rson],void();	
	}
};
vector<pair<pair<int,int>,int>> upd[MAXN];
int solve(int st) {
	ffor(i,1,n) upd[i].clear();
	ffor(s,1,k) if(st&(1<<s-1)) ffor(i,1,n) {
		ffor(j,s,occ[i].size()-2) {
			//(occ[i][j-s],occ[i][j-s+1]~[occ[i][j],occ[i][j+1])
			upd[occ[i][j]].push_back({{occ[i][j-s]+1,occ[i][j-s+1]},1});
			upd[occ[i][j+1]].push_back({{occ[i][j-s]+1,occ[i][j-s+1]},-1});
		}
	}
	int ans=0;
	DS::build(1,1,n);
	ffor(i,1,n) {
		for(auto pr:upd[i]) {
			int x=pr.first.first,y=pr.first.second,d=pr.second;
			DS::update(1,1,n,x,y,d);	
		}
		if(DS::t[1].mn==0) ans+=n-DS::t[1].cnt;
		else ans+=n;
	}
	return ans;
}
signed main() {
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	ffor(i,1,n) occ[i].push_back(0);
	ffor(i,1,n) cin>>a[i],occ[a[i]].push_back(i);
	ffor(i,1,n) occ[i].push_back(n+1);
	ffor(i,1,(1<<k)-1) {
		int res=solve(i);
		if(__builtin_popcount(i)%2==1) ans+=res;
		else ans-=res;	
	}
	cout<<ans;
	return 0;
}
